package _dp_base;

import java.util.ArrayList;

/**
 * 1964. 找出到每个位置为止最长的有效障碍赛跑路线
 */
public class No1964 {
    private int[] obstacles;

    /**
     * 1. 递归（会超时）
     */
    public int[] longestObstacleCourseAtEachPosition1(int[] obstacles) {
        int n = obstacles.length;
        this.obstacles = obstacles;

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = dfs(i);
        }
        return answer;
    }

    private int dfs(int i) {
        int maxLen = 1;
        for (int j = 0; j < i; j++) {
            if (obstacles[j] <= obstacles[i]) {
                int preMaxLen = dfs(j);
                if (preMaxLen + 1 > maxLen) {
                    maxLen = preMaxLen + 1;
                }
            }
        }
        return maxLen;
    }

    /**
     * 2. 迭代（会超时）
     */
    public int[] longestObstacleCourseAtEachPosition2(int[] obstacles) {
        int n = obstacles.length;

        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (obstacles[j] <= obstacles[i]) {
                    if (f[j] + 1 > f[i]) {
                        f[i] = f[j] + 1;
                    }
                }
            }
        }
        return f;
    }

    private ArrayList<Integer> list;

    /**
     * 3. 贪心 + 二分查找
     */
    public int[] longestObstacleCourseAtEachPosition3(int[] obstacles) {
        int n = obstacles.length;
        list = new ArrayList<>();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int index = lowerBound(obstacles[i] + 1);
            if (index == list.size()) list.add(obstacles[i]);
            else list.set(index, obstacles[i]);
            ans[i] = index + 1;
        }
        return ans;
    }

    private int lowerBound(int x) {
        int n = list.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (list.get(mid) < x) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
